package com.二叉树的下一个节点;

public class SolutionBetter {

	public TreeLinkNode GetNext(TreeLinkNode node) {
		if (node == null)
			return null;
		if (node.right != null) { // 如果有右子树，则找右子树的最左节点
			node = node.right;
			while (node.left != null)
				node = node.left;
			return node;
		}
		while (node.next != null) { // 没右子树，则找第一个当前节点是父节点左孩子的节点
			if (node.next.left == node)
				return node.next;
			node = node.next;
		}
		return null; // 退到了根节点仍没找到，则返回null
	}
}
